package Leetcode.动态规划;

/**
 * @ClassName 礼物最大值
 * @since: 2023/7/22 15:55
 * @auth: kirito
 * @description: 在一个 m*n 的棋盘的每一格都放有一个礼物，
 * 每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，
 * 并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 *输入:
 * [
 *   [1,3,1],
 *   [1,5,1],
 *   [4,2,1]
 * ]
 * 输出: 12
 * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

 **/
public class 礼物最大值 {
    public static int maxValue(int[][] grid) {
        int i = grid.length;
        int j = grid[0].length;
        int[][] dp = new int[i][j];
        dp[0][0] = grid[0][0];
        for (int q = 1; q < i; q++) {
            dp[q][0] = grid[q][0]+dp[q-1][0];
        }
        for (int q = 1; q < j; q++) {
            dp[0][q] = grid[0][q]+dp[0][q-1];
        }
        for(int q = 1;q<i;q++){
            for (int w = 1; w < j; w++) {
                dp[q][w] = Math.max(dp[q-1][w]+grid[q][w],
                                    dp[q][w-1]+grid[q][w]);
            }
        }
        for(int q = 0;q<i;q++){
            for (int w = 0; w < j; w++) {
                System.out.print(dp[q][w]+"  ");
            }
            System.out.println();
        }
        return dp[i - 1][j - 1];
    }

    public static void main(String[] args) {
        int[][] matrix = {
//                {1, 3, 1},
//                {1, 5, 1},
//                {4, 2, 1}
                {1,2,5},
                {3,2,1}
        };
        System.out.println(maxValue(matrix));
    }
}
